#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
@File Name: 优化_使用字典类型实现集合_fastset.py
@Author: LT
@Date: 2021/9/27 14:56
# -----------------------------------------------------------------------------------------------------
@Description: 
for循环和in扫描会呈指数级变慢，所以考虑用字典来作为它的底层实现。

集合的元素可以被存储为字典的 键 ，而对应的值可以都设为None。这样就可以替代for in 的扫描，采用哈希suo
# -----------------------------------------------------------------------------------------------------
"""
# import 普通集合类_set as set
import 普通集合类_set as set


class Set(set.Set):
    def __init__(self, value=None):
        if value is None:
            value = []
        self.data = {}                      # 这里使用字典而非self.data = []
        self.concat(value)                  # 实例初始化就已经把self.data，使用字典键去重了

    def intersect(self, other):
        res = {}
        for x in other:                     # other是一个序列或者集合
            if x in self.data:
                res[x] = None
        return Set(res.keys())

    def union(self, other):
        res = {}
        for x in other:
            res[x] = None
        for x in self.data.keys():          # '&' 和 '|'都是哈希表查询，所以它们都是很快速
            res[x] = None
        return Set(res.keys())

    def concat(self, value):
        for x in value:
            self.data[x] = None

    # 继承and、or和len方法
    def __getitem__(self, item):
        return list(self.data.keys())[item]

    def __repr__(self):
        return "<Set:%r>" % list(self.data.keys())


if __name__ == '__main__':
    pass
